The network availability differs in the Quality of Service (QoS) of different network services and constrains each other with performance expense. In order to solve the problems, Markov chain theory was introduced, a new Markov Chain and QoS based Network Availability (MCQNA) evaluation model was constructed on the basis of defining the matching degree of service capability based on the minimum service expense. Firstly, starting from the QoS indicator that could best reflect the characteristics of network availability and considering the performance overhead, the cost function was defined and the state transition matrix was given. Then, through the analysis of relationship between stationary state and network availability, the stationary distribution was solved and used as the dynamic weight of operation cost of QoS. The network availability evaluation characterized by the minimum operation cost of service was realized. The simulation results show that, the ergodic transition matrix constructed by the proposed model has the stationary distribution, and it is feasible to evaluate the network availability. According to the QoS standards of different services, the proposed model can be used to measure the network availability effectively for specific services.